In a transmission of data over a digital communication network, such as an asynchronous transfer mode or ATM network, flows of data from a source of the network, called a source end system, to a destination of the network, called a destination end system, are organized into virtual connections, where each virtual connection represents the flow of data from a specific user or computer program at a specific source end system to another specific user or computer program at another specific destination end system down a virtual channel. The network carries the data of many virtual connections through its links, with switching of data between links occurring at intermediate switch nodes in the network, accomplished by intermediate systems at these nodes. The data of each virtual connection follows a path or channel through the network that is fixed when the virtual connection is initialized.
Problems arise when multiple sources send data cells or packets at widely varying rates through a switch node or link of the network at an aggregated rate which taxes the ability of that switch node or link to handle the data. Congestion occurs at the node of a network when data arrives at the node at a rate exceeding the rate at which the node can process and forward the data to other nodes. The excess data then accumulates in buffer storage at the node, which fills at a rate which is the difference between the arrival rate and the processing and forwarding rate. If the congestion persists for long periods of time, the buffer storage will be filled to maximum capacity and any additional data must be discarded.
In an effort to minimize such data loss, two types of systems have been used at a source to prevent or inhibit excess data from entering the network. One such system is a rate-based system in which the rate at which the data is permitted to enter the network is adjusted via a feedback signal transmitted back to the source reflecting the congestion of the network. This congestion of the network is typically denoted by an explicit forward congestion indication bit or an explicit rate in the form of Resource Management cells fed back to the source. One such rate controlled system is described in an ATM Forum document #94-0735 entitled "Enhanced PRCA (Proportional Rate-Control Algorithm)" authored by Larry Roberts, August 1994. Additional details of this system are described in ATM Forum document #94-0983R1 entitled "Explicit Rate Performance Evaluations" authored by Andrew S. Barnhart, October 1994, and in ATM Forum document #94-1110 entitled "Proposal for Example Pseudocode for the End-System" authored by Andrew W. Barnhart, Nov. 28, 1994.
A competing system for controlling data transmission uses a credit control approach which guarantees lossless transmission of data cells. The credits are generated starting at a destination node to reflect its ability to receive data. This credit is transmitted back to the next upstream node where this credit is interpreted and modified based on this node's ability to receive data. The process continues through each intermediate node back to the source-where the credit at the source reflects all intermediate credits as well as the one from the destination. Typically the credits are numbers reflecting the unused buffer space at each node. The source then interprets the credit as an indication of the amount of data that it can transmit into the network without any data loss due to congestion or buffer overflow. Note that data rate is not controlled, but the number of cells transmitted is controlled. One such credit controlled system is described in an ATM Forum document #94-0632 entitled "Credit-Based FCVC Proposal for ATM Traffic Management, Revision R2" authored by Doug Hunt, Warner Andrews, Jim Scott, Bob Simcoe, Jon Bennett, H. T. Kung, John Howard, Alan Chapman, and Ken Brinkerhoff, July, 1994.
Each scheme has its advantages and disadvantages. The rate-based scheme relies on systems at either end of the network to do traffic control. Thus very little intelligence and participation are required on the part of switch nodes of ATM networks. Also, the rate-based paradigm is in accordance with the current standards for ATM traffic management to be implemented on network interface hardware. However, the issues of performance and its ability to react to congestion have been raised about the rate-based scheme. There is no analytical proof or real world experience showing that the rate-based scheme will be able to provide satisfactory performance and minimize cell losses of bursty traffic. Furthermore, achieving nearly lossless transmission in a practical network depends on the particular characteristics of the data flows of the virtual connections being carried by that network.
The credit-based scheme, on the other hand, has a solid proof that lossless transmission can be achieved. With its static buffer allocation algorithm, it can also achieve the maximum link bandwidth utilization. However, the credit-based scheme requires coordination and active participation of all switches and intermediate systems in the path of a data flow being controlled. Furthermore, in the prior art, credit-based schemes have been applied on a link-by-link or hop-by-hop basis, thus requiring intermediate systems to be able to reduce, inhibit, or otherwise control the flow of data already sent by the source of one virtual connection while letting the flows of other virtual connections proceed.
This requirement imposes a cost and complexity on switches and intermediate systems greatly in excess of those in networks with rate-based flow control. More specifically, each such switch or intermediate system must include means for maintaining a queue of data cells for each virtual connection so that the cells of any virtual connection can be transmitted by this switch or intermediate system independently of those of other virtual connections. Such means are not required at switches and intermediate systems in networks with rate-based flow control because the rate-based method causes the source of each connection to control the flow of data of its connection at the point where the data enters the network. Thus, in rate-based networks, cells arriving at an intermediate system from many different sources representing many different virtual connections may be combined into one or more queues without reference to the connections to which they each belong. This represents a great savings in the cost and complexity of the switches and intermediate systems.
A combined scheme incorporating credit-based flow control and rate-based flow control has been described in U.S. patent application Ser. No. 08/271,418 entitled "Credit/Rate Based System for Controlling Traffic in a Digital Communication Network" by Qin Zheng, Hugh C. Lauer, and John H. Howard, filed Jul. 6, 1994, incorporated herein by reference, and assigned to the assignee hereof. Another such combined system is described in U.S. patent application Ser. No. 08/297,270 entitled "Credit Enhanced Proportional Rate Control System" by Qin Zheng, filed Aug. 17, 1994, incorporated herein by referenced and assigned to the assignee hereof. However, these schemes also include the requirement of separate queues of buffers for each virtual connection to enable an intermediate system at a switch node to reduce or inhibit the flow of data already sent by one virtual connection while continuing to allow the flows of other virtual connections to proceed. Because of the queueing requirement for each virtual connection at each switch, these systems are subject to levels of cost and complexity similar to credit-only systems.
By way of further background, note that end-to-end flow control systems are widely known in digital communications networks. For example, end-to-end and hop-by-hop flow control techniques are compared by John D. Spragins, Joseph L. Hammond, and Krzysztof Pawlikowski in a book entitled "Telecommunications: Protocols and Design," published by Addision-Wesley, 1991, pages 407-410. The window-based flow control method of the widely used protocol TCP/IP is described by Douglas E. Comer and David L. Stevens in a book entitled "Internetworking with TCP/IP," published by Prentice Hall in 1991. End-to-end flow control techniques in ATM networks are described in "Asyn-chronous Transfer Mode Networks: Performance Issues" authored by Raif O. Onvural and published by Artech House, 1994.